package com.linyaonan.leetcode.medium._2779;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。
 *
 * 在一步操作中，你可以执行下述指令：
 *
 * 在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。
 * 将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数。
 * 数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。
 *
 * 对数组 nums 执行上述操作任意次后，返回数组可能取得的 最大 美丽值。
 *
 * 注意：你 只 能对每个下标执行 一次 此操作。
 *
 * 数组的 子序列 定义是：经由原数组删除一些元素（也可能不删除）得到的一个新数组，且在此过程中剩余元素的顺序不发生改变。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [4,6,1,2], k = 2
 * 输出：3
 * 解释：在这个示例中，我们执行下述操作：
 * - 选择下标 1 ，将其替换为 4（从范围 [4,8] 中选出），此时 nums = [4,4,1,2] 。
 * - 选择下标 3 ，将其替换为 4（从范围 [0,4] 中选出），此时 nums = [4,4,1,4] 。
 * 执行上述操作后，数组的美丽值是 3（子序列由下标 0 、1 、3 对应的元素组成）。
 * 可以证明 3 是我们可以得到的由相等元素组成的最长子序列长度。
 * 示例 2：
 *
 * 输入：nums = [1,1,1,1], k = 10
 * 输出：4
 * 解释：在这个示例中，我们无需执行任何操作。
 * 数组 nums 的美丽值是 4（整个数组）。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 10^5
 * 0 <= nums[i], k <= 10^5
 *
 * @author: Lin
 * @date: 2024/10/29
 */
public class MaximumBeautyOfAnArrayAfterApplyingOperation {

    /**
     * 按照[4,6,1,2],k=2进行分析可以转换为：[[2-6],[4-8],[-1,3],[0,4]] 求连续区间个数，可以发现0-8涵盖了三个区间
     *
     * 由于k是固定的，那么原始数组进行转换后的区间也必定是符合原有数据规则的，所以先将原始数据排序：
     *
     * [1,2,4,6] => [-1,3],[0,4],[2,6],[4,8]
     *
     * [x-k,x+k] 到 [y-k,y+k] 如果中间有相交的部分则表示可以组成合适的数值及x+k >= y-k =>  2k >= y - x
     *
     * @param nums
     * @param k
     * @return
     */
    public int maximumBeauty(int[] nums, int k) {
        Arrays.sort(nums);

        int l = 0;
        int r = 0;
        int result = 0;
        while (l <= r && r < nums.length) {
            while (nums[r] - nums[l] > 2 * k) {
                l++;
            }
            result = Math.max(result, r - l + 1);
            r++;
        }
        return result;
    }

}
